#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<int> s(len + 1);
        s[len - 1] = prices[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            s[i] = max(prices[i], s[i + 1]);
        }
        int ans = 0;
        for (int i = 0; i < len - 1; i++) {
            ans = max(s[i + 1] - prices[i], ans);
        }
        return max(ans, 0);
    }
};